Clustering Algorithm for High Dimensional Data Stream Based on Projection and Density

doi:10.3969 /j.issn.1674-0696.2013.04.41

Abstract

Abstract: A clustering algorithm for high dimensional data stream based on the projection and density ( HpDenStream) is proposed，which is based on the classical data stream clustering algorithm． This algorithm combines with the sliding window technical，and it uses the projection clustering algorithm to reduce the data dimensionality of dimensional data streams and then adopts the density clustering algorithm to detect the anomaly data detection． The simulation results show that the algorithm not only takes up smaller storage space and less workload，but also improves the efficiency of the implementation of the algorithm．

Key words: data stream, clustering algorithm, projection, dimension reduction, density, anomaly detection

摘要： 在经典数据流的聚类算法基础之上，提出了一种基于投影和密度的高维数据流聚类算法———HpDenStream，该算法结合滑动窗口技术，采用投影算法对高维数据流进行降维处理，并运用密度聚类算法对降维后的数据进行异常数据检测。仿真实验结果表明: 该方法占用的存储空间小，算法的工作量少，并提高了算法的执行效率。

关键词: 数据流, 聚类算法, 投影, 降维, 密度, 异常检测

CLC Number:

TP392

Wang Ｒenhong，Wang Jiawei，Liang Zongbao. Clustering Algorithm for High Dimensional Data Stream Based on Projection and Density[J]. Journal of Chongqing Jiaotong University(Natural Science), 2013, 32(4): 725-728.

汪仁红，王家伟，梁宗保. 基于投影和密度的高维数据流聚类算法[J]. 重庆交通大学学报（自然科学版）, 2013, 32(4): 725-728.

References

[1] 汪成亮，陆志坚，庞栩．一种数据流趋势分析方法的研究与应用[J]．计算机系统应用，2010， 19( 1) : 152-155．
Wang Chengliang，Lu Zhijian，Pang Xu．Ｒesearch and application of an algorithm for trend analysis of data streams [J]． Computer System ＆ Application，2010，19( 1) : 152-155．
[2] 黄树成，曲亚辉．数据流分类技术研究综述[J]．计算机应用研究， 2009，26( 10) : 3604-3609．
Huang Shucheng，Qu Yahui． Survey on data streams classification technologies[J]． Application Ｒesearch of Computers，2009，26( 10) : 3604-3609．
[3] Guha S，Mishra N，Motwani Ｒ，et al． Clustering Data Streams [C]/ /Proceedings of the 41st Annual Symposium on Foundations of Computer Science． California: IEEE，2000: 71-80．
[4] 张继超．数据流的变化检测算法及其在实时汇率数据流异常检测中的应用[D]．郑州: 郑州大学，2005．
Zhang Jichao． Change Detection Scheme of Data Stream and the Application of Detecting the Abnormal Data Blocks in Exchange Ｒate Data Stream[D]． Zhengzhou: Zhengzhou University，2005．
[5] 史金成．基于相关性的数据流聚类及其应用研究[D]．合肥: 合肥工业大学， 2007．
Shi Jincheng．Ｒesearch on Data Stream Clustering and its Applications Based on Correlations [D]． Hefei: Hefei University of Technology，2007．
[6] Xu Ｒui，Donald Wunsch． Survey of clustering algorithms [J]．IEEE Transactions on Neural Networks，2005，16( 3) : 634-678．
[7] 陈铭，吉根林．一种基于相似维的高维子空间聚类算法[J]．南京师大学报: 自然科学版，2010， 33( 4) : 119-122．
Chen Ming，Ji Genlin． A subspace clustering algorithm for high dimensional data based on similar dimension [J]． Journal of NanjingNormal University: Natural Science，2010，33( 4) : 119-122．
[8] 任家东，周玮玮，何海涛．高维数据流的自适应子空间聚类算法[J]．计算机科学与探索， 2010，4( 9) : 859-964．
Ｒen Jiadong，Zhou Weiwei，He Haitao． Adaptive clustering algorithm for mining subspace clusters in high-dimensional data stream[J]． Journal of Frontiers of Computer Science and Technology，2010，4( 9) : 859-964．
[9] 颜晓龙，沈鸿．一种适用于高维数据流的子空间聚类方法[J]．计算机应用， 2007， 27( 7) : 1680-1684． Yan Xiaolong，Shen Hong． Subspace clustering method for high dimensional data streams [J]． Computer Applications，2007，27( 7) : 1680-1684．
[10] 周晓云，孙志挥，张柏礼，等．高维数据流子空间聚类发现及维护算法[J]．计算机研究与发展， 2006，43( 5) : 834-840．
Zhou Xiaoyun，Sun Zhihui，Zhang Baili，et al． An efficient discovering and maintenance algorithm of subspace clustering over high dimensional data streams[J]． Journal of Computer Ｒesearch and Development，2006，43( 5) : 834-840．
[11] 李子杰，郑成．流数据和传统数据存储及管理方法比较研究[J]．计算机技术与发展，2009，19( 4) : 101-104．
Li Zijie，Zheng Cheng． Comparative study on methods of storage and management of stream and traditional data [J]． Computer Technology and Development，2009，19( 4) : 101-104．
[12] 王家伟，汪仁红，罗宪，等．基于数据流的桥梁健康监测海量数据处理[J]．计算机系统应用，2011，20( 12) : 158-161．
Wang Jiawei，Wang Ｒenhong，Luo Xian，et al． Processing of massive data based on data stream and bridge health monitoring[J]． Computer System ＆ Application，2011，20( 12) : 158-161．

[1]	LI Nan, QIANG Yigeng, FAN Rui. Aircraft Flight Trajectory Clustering Based on Trajectory Compression [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(01): 1-6.
[2]	YE Zhen, HE Mingguang, LIANG Keke. Location Method of Taxi Service Stations Based on Service Demands [J]. Journal of Chongqing Jiaotong University(Natural Science), 2019, 38(03): 75-82.
[3]	LI Tianhua1, ZHAO Xin2, ZHANG Kejia1, TIAN Zhenou2,BAI Wenying1. Load Model of Vehicles Idling Congestion on Urban Bridge Based on Measured Traffic Data [J]. Journal of Chongqing Jiaotong University(Natural Science), 2019, 38(02): 126-132.
[4]	LI Yongpan1, 2, LIU Zhengjiang1, ZHENG Zhongyi1. Clustering Analysis Method of Shipborne AIS Data Based on Spatio-Temporal Density [J]. Journal of Chongqing Jiaotong University(Natural Science), 2018, 37(10): 117-122.
[5]	PENG Bo, CAI Xiaoyu, LI Shaobo, ZHANG Youjie. Automatic Crack Detection Algorithm Based on 3D Virtual Pavement [J]. Journal of Chongqing Jiaotong University(Natural Science), 2018, 37(1): 46-53.
[6]	TANG Shengchuan1, FENG Deng2,3, WANG Junjie2,3. Stereographic-Real Proportion Projection Method and Its Application [J]. Journal of Chongqing Jiaotong University(Natural Science), 2018, 37(08): 63-68.
[7]	SONG Jinhua，JI Yuping，LIU Zhilei，ZHANG Xuesong，NI Dongxu. Mixture Proportion Design of High-Performance RAP Materials [J]. Journal of Chongqing Jiaotong University(Natural Science), 2017, 36(6): 38-47.
[8]	ZOU Changjun，YIN Yong，LIU Xiuwen，LI Haijiang. Research and Implementation of a New Method of Visualization of Oil Spill at Sea Surface [J]. Journal of Chongqing Jiaotong University(Natural Science), 2017, 36(6): 103-108.
[9]	ZHANG Furen, HE Xiaonan, LI Na ,TAO Jiaxiang, ZHU Shibao. The Effect of the Leeward Wall Heat Flux on the Particle Concentration Distribution of the Buildings [J]. Journal of Chongqing Jiaotong University(Natural Science), 2016, 35(5): 103-109.
[10]	HUANG Wentao, ZHOU Ping, CHENG Jinxiang. An Estimation Method of Engineering Cost Based on Adaboost and Variable Selection with LSSVM [J]. Journal of Chongqing Jiaotong University(Natural Science), 2016, 35(3): 54-57.
[11]	Huang Chengfeng, Zhao Guanghui, Wang Ping. Evaluation and Application of Traffic Safety Facilities on Rural Road in Mountain Area Based on HSM —A Case Study of Bend Sections [J]. Journal of Chongqing Jiaotong University(Natural Science), 2015, 34(5): 89-94.
[12]	Yang Jun, Yang Zhi, Zhang Guodong, Tang Yunwei. Swelling Force of Weathered Sand of Improved Expansive Soil [J]. Journal of Chongqing Jiaotong University(Natural Science), 2014, 33(4): 106-109.
[13]	Wang Qingfeng , Peng Junjie , Liu Changfa. Theor.etical and Experimental Investigation on S-Wave Propagation of Soil-Stone Medium [J]. Journal of Chongqing Jiaotong University(Natural Science), 2014, 33(1): 94-97.
[14]	Liu Shanhong. Damage Mechanism and Prevention Countermeasures of HDPE Protecting Sheath of Stayed Cables [J]. Journal of Chongqing Jiaotong University(Natural Science), 2013, 32(增1): 888-893.
[15]	Gao Yuanyuan，Zhong Yang，Li Ｒui. Theoretical Analysis on Influence of Overlay on Crack Ｒesistance of Old Cement Pavement [J]. Journal of Chongqing Jiaotong University(Natural Science), 2013, 32(5): 943-949.